# -*- coding: utf-8
#
# Программа к учебному пособию
# К.Ю. Поляков. Программирование на языках Python и C++
# Часть 3 (10 класс)
# Программа № 35. Динамическое программирование.
#                 Количество программ для исполнителя

# здесь нужно ввести a, b, M, N
a = 1
b = 2
M = 3
N = 25

K = [0]*(N+1)  # заполняем массив нулями
K[M] = 1       # начальное значение
for i in range(M+1,N+1):
  if i-a >= 0:
    K[i] = K[i-a]
  else:
    K[i] = 0
  if i % b == 0:    # если может быть команда 2
    K[i] += K[i//b]

print( K )
print( K[N] )